1. Field of the Invention
The disclosed embodiments of the present invention relate to a method for determining a parity check matrix utilized in a flash memory system, and more particularly, to a method for determining a low-density parity check based parity check matrix utilized to decode data stored in the flash memory system by exhaustively calculating a plurality of estimated results corresponding to any possible candidate blocks.
2. Description of the Prior Art
Communication of information between computers and other electronic devices can be implemented using any of a variety of different standards and technologies. Channel coding and error correction techniques may be used to reduce errors in received signals introduced from distortion and other disturbances. Such coding and error correction may be implemented using an encoder and a decoder at the ends of the transmission channel.
For example, any algorithm for low-density parity check (LDPC) codes may be used in a flash memory system to encode the received data, and the encoded data (codeword) can be then stored in a flash memory. On the other hand, iterative decoders are often used to converge on a correct decoded value while decoding the codeword. In one implementation, LDPC decoding is performed in the receiving end using a soft-decision, message-passing algorithm (MPA). The received bits (e.g., channel values) are treated as variables each representing the probability of the value being a “0” or a “1”, and the variables are represented in the decoding algorithm as log likelihood ratios (LLRs). The message-passing algorithm passes messages (e.g., LLRs) from the variable nodes to the check nodes, calculates the syndrome of the current iteration, passes messages (e.g., LLRs) from the check nodes to the variable nodes, and iterates in this same way until a convergence is reached (e.g., check bits of the syndrome are all 0's).
However, one of the problems inherent to LDPC codes is the presence of trapping set(s). A trapping set is the set of bits that cannot be decoded to the correct values after any given number of iterations. Regarding an LDPC decoder with high signal-to-noise (SNR) additive white Gaussian noise (AWGN), an error type is a small trapping set. In general, the error bit number of the received bits is usually small. However, if the errors are located at some specific variable nodes, they would feed back wrong reliability values and cause a trapping set. To put it simply, when decoding a received codeword, an LDPC decoder may encounter one or more trapping sets that prevent the decoder from properly decoding the received codeword. The minimum bit error rate of a specific LDPC code may be dominated by the number of trapping sets inherently existed in the LDPC code.
Thus, there is a need for effectively finding or determining a LDPC code which inherently has a minimum number of trapping set(s). In the other words, there is a need for effectively finding or determining a parity check matrix for defining a LDPC code which has a best performance in error correction.